On the Chomsky normal form
Given a context-free grammar G, describe a polynomial time procedure to obtain a grammar G' producing the same language of G and in Chomsky Normal Form.
Given a grammar G in Chomsky normal form and a word w produced by G, in how many steps is w produced? (as a function of |w|)
Recall that a context-free grammar G is in Chomsky normal form if all of its production rules are of the form:
\begin{aligned} A &\to BC, \text{or} \\ A &\to a, \text{or} \\ S &\to \lambda, \end{aligned} where A, B, and C are nonterminal symbols, the letter a is a terminal symbol, and S is the start symbol. Moreover, neither B nor C may be the start symbol S, and the production rule S\to \lambda can only appear if \lambda is in the language produced by G.